package com.ljx.SlidingWindow;

import com.sun.org.apache.bcel.internal.generic.NEW;

import java.util.HashMap;

/**
 * @author 李加喜
 * @Package com.ljx.SlidingWindow
 * @date 2021-11-09 22:01
 */
// 判断s2中是否包含s1的子串
public class StringPaiLie {
    public static void main(String[] args) {
        StringPaiLie lie = new StringPaiLie();
        System.out.println(lie.checkInclusion("ab","eidbaooo"));
    }
    public boolean checkInclusion(String s1, String s2) {
        HashMap<Character, Integer> need = new HashMap<Character, Integer>(16);
        HashMap<Character, Integer> window = new HashMap<>(16);
        char[] ts = s1.toCharArray();
        for (char s1s : ts) {
            need.put(s1s, need.getOrDefault(s1s, 0) + 1);
        }
        int left = 0, right = 0;
        // 记录的是滑动窗口的数量
        int valid = 0;
        char[] sList = s2.toCharArray();
        while (right<sList.length){
            char c=sList[right];
            right++;
            //更新窗口内容
            if (need.containsKey(c)){
                window.put(c,window.getOrDefault(c,0)+1);
                if (need.get(c).equals(window.get(c))){
                    valid++;
                }
            }
            // 判断是否缩小
            while (right-left>=ts.length){
                if (valid==need.size()){
                    return true;
                }
                char d=sList[left];
                left++;
                if (need.containsKey(d)){
                    if (window.get(d).equals(need.get(d))){
                        valid--;
                    }
                    window.put(d,window.getOrDefault(d,0)-1);
                }
            }
        }
        return false;
    }
}
